
package net.lab0.electron.map;


import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;


/**
 * Quad tree
 * 
 * @author 116
 * 
 */
public class QuadTreeNode<T extends My2DPointInterface>
implements Iterable<T>
{
	/**
	 * Les éléments contenus dans cette node.
	 */
	private ArrayList<T>				elements	= new ArrayList<T>();
	
	/**
	 * la racine de l'arbre
	 */
	private QuadTreeRoot<T>				treeRoot;
	
	/**
	 * la node parent
	 */
	private QuadTreeNode<T>				parent;
	
	/**
	 * Les branches et feuilles cette node.
	 */
	private ArrayList<QuadTreeNode<T>>	children	= null;
	
	/**
	 * le point de s�paration des �l�ments pour cette node
	 */
	private Point2D.Double				splitPoint	= null;
	
	/**
	 * les limites de cette node
	 */
	private Rectangle2D.Double			bounds		= null;
	
	/**
	 * le niveau d'imbrication de cette node. La node racine a une profondeur de 0.
	 */
	private int							depth;
	
	/**
	 * la position dans la node parent, selon le schéma suivant
	 * 
	 * <pre>
	 * +--------+--------+
	 * | NW = 0 | NE = 1 |
	 * +--------+--------+
	 * | SW = 2 | SE = 3 |
	 * +--------+--------+
	 * 
	 * root : 4
	 * </pre>
	 * 
	 */
	private int							positionInParentNode;
	
	private static final int			NW			= 0;
	private static final int			NE			= 1;
	private static final int			SW			= 2;
	private static final int			SE			= 3;
	
	private static final int[]			zones		= { NW, NE, SW, SE };
	
	private static final int			ROOT		= 4;

	protected QuadTreeNode(QuadTreeRoot<T> treeRoot, Collection<T> elementsToAdd, Rectangle2D.Double bounds)
	{
		this(treeRoot,bounds);
		addAll(elementsToAdd);
	}
	protected QuadTreeNode(QuadTreeRoot<T> treeRoot, Rectangle2D.Double bounds)
	{
		this.depth = 0;
		this.parent = null;
		this.bounds = bounds;
		this.treeRoot = treeRoot;
		this.positionInParentNode = ROOT;
	}
	
	protected QuadTreeNode(QuadTreeNode<T> parent, int positionInParentNode)
	{
		this.parent = parent;
		this.depth = parent.depth + 1;
		this.treeRoot = parent.treeRoot;
		this.positionInParentNode = positionInParentNode;
		
		switch (positionInParentNode)
		{
			case NE:
				bounds = new Rectangle2D.Double(parent.splitPoint.x, parent.bounds.y, parent.bounds.x
				+ parent.bounds.width - parent.bounds.x, parent.bounds.y - parent.splitPoint.y);
				break;
			
			case NW:
				bounds = new Rectangle2D.Double(parent.bounds.x, parent.bounds.y,
				parent.splitPoint.x - parent.bounds.x, parent.bounds.y - parent.splitPoint.y);
				break;
			
			case SE:
				bounds = new Rectangle2D.Double(parent.splitPoint.x, parent.splitPoint.y, parent.splitPoint.x
				- (parent.bounds.x + parent.bounds.width), parent.splitPoint.y
				- (parent.bounds.y - parent.bounds.height));
				break;
			
			case SW:
				bounds = new Rectangle2D.Double(parent.bounds.x, parent.splitPoint.y, parent.splitPoint.x
				- parent.bounds.x, parent.splitPoint.y - (parent.bounds.y - parent.bounds.height));
				break;
			
		}
	}
	
	private void splitAndClear(Collection<? extends T> elements)
	{
		getSplitPoint();
		if (children == null)
		{
			children = new ArrayList<QuadTreeNode<T>>(4);
			for (int zone : zones)
			{
				children.add(new QuadTreeNode<T>(this, zone));
			}
		}
		
		ArrayList<T> nw = new ArrayList<T>();
		ArrayList<T> ne = new ArrayList<T>();
		ArrayList<T> sw = new ArrayList<T>();
		ArrayList<T> se = new ArrayList<T>();
		
		for (T p : elements)
		{
			if (p.getX() > splitPoint.x)
			{
				if (p.getY() > splitPoint.y)
				{
					ne.add(p);
				}
				else
				{
					se.add(p);
				}
			}
			else
			{
				if (p.getY() > splitPoint.y)
				{
					nw.add(p);
				}
				else
				{
					sw.add(p);
				}
			}
		}
		
		// System.out.println("Splitted in 4 blocks : " + ne.size() + "/" +
		// nw.size() + "/" + se.size() + "/" + sw.size());
		
		elements.clear();
		
		children.get(NE).addAll(ne);
		children.get(NW).addAll(nw);
		children.get(SE).addAll(se);
		children.get(SW).addAll(sw);
	}
	
	private Double getSplitPoint()
	{
		if (splitPoint == null)
		{
			splitPoint = new Point2D.Double(bounds.x + bounds.width / 2, bounds.y - bounds.height / 2);
		}
		return splitPoint;
	}
	
	public String getNodePath()
	{
		if (parent == null)
		{
			return "" + positionInParentNode;
		}
		else
		{
			return parent.getNodePath() + "." + positionInParentNode;
		}
	}
	
	protected void getPointsInRectangle(Rectangle2D.Double rect, ArrayList<T> list)
	{
// System.out.println("searching in : " + getNodePath());
		
		double maxX = rect.x + rect.width;
		double maxY = rect.y;
		double minX = rect.x;
		double minY = rect.y - rect.height;
		
		if (children == null)
		{
// System.out.println("searching in : " + getNodePath());
			for (T e : elements)
			{
				if (e.getX() > minX && e.getX() < maxX && e.getY() > minY && e.getY() < maxY)
				{
					list.add(e);
				}
			}
		}
		else if (this.bounds.x >= rect.x && this.bounds.width + this.bounds.x <= rect.width + rect.x && this.bounds.y <= rect.y
		&& this.bounds.y - this.bounds.height >= rect.y - rect.height)
		{
			list.addAll(getAllMapElements());
		}
		else
		{
			if (splitPoint.x <= minX) // le split est à gauche du rectangle
			{
				if (splitPoint.y <= minY)
				{
					children.get(NE).getPointsInRectangle(rect,list);
				}
				else if (splitPoint.y >= maxY)
				{
					children.get(SE).getPointsInRectangle(rect,list);
				}
				else
				{
					children.get(SE).getPointsInRectangle(rect,list);
					children.get(NE).getPointsInRectangle(rect,list);
				}
			}
			else if (splitPoint.x >= maxX) // le split est à droite du rectangle
			{
				if (splitPoint.y <= minY)
				{
					children.get(NW).getPointsInRectangle(rect,list);
				}
				else if (splitPoint.y >= maxY)
				{
					children.get(SW).getPointsInRectangle(rect,list);
				}
				else
				{
					children.get(SW).getPointsInRectangle(rect,list);
					children.get(NW).getPointsInRectangle(rect,list);
				}
			}
			else
			// le split est au centre du rectangle en x
			{
				if (splitPoint.y <= minY)
				{
					children.get(NW).getPointsInRectangle(rect,list);
					children.get(NE).getPointsInRectangle(rect,list);
				}
				else if (splitPoint.y >= maxY)
				{
					children.get(SW).getPointsInRectangle(rect,list);
					children.get(SE).getPointsInRectangle(rect,list);
				}
				else
				{
					children.get(SW).getPointsInRectangle(rect,list);
					children.get(NW).getPointsInRectangle(rect,list);
					children.get(SE).getPointsInRectangle(rect,list);
					children.get(NE).getPointsInRectangle(rect,list);
				}
			}
		}
	}
	
	protected Collection<T> getAllMapElements()
	{
		if (children == null)
		{
			return elements;
		}
		else
		{
			ArrayList<T> ret = new ArrayList<T>();
			for (QuadTreeNode<T> n : children)
			{
				ret.addAll(n.getAllMapElements());
			}
			return ret;
		}
	}
	
	protected List<QuadTreeNode<T>> getAllNodes()
	{
		List<QuadTreeNode<T>> nodes = new ArrayList<QuadTreeNode<T>>();
		if (children != null)
		{
			for (QuadTreeNode<T> child : children)
			{
				nodes.addAll(child.getAllNodes());
			}
		}
		
		nodes.add(this);
		
		return nodes;
	}
	
	/**
	 * 
	 * @return Le nombre de <code>T</code> dans cette node et ses fils.
	 */
	public int size()
	{
		if (this.children != null)
		{
			int size = 0;
			for (QuadTreeNode<T> child : children)
			{
				size += child.size();
			}
			return size;
		}
		else
		{
			return elements.size();
		}
	}
	
	public boolean isEmpty()
	{
		return size() == 0;
	}
	
	public boolean contains(Object o)
	{
		if (o == null)
		{
			return false;
		}
		else if (!(o instanceof My2DPointInterface))
		{
			return false;
		}
		else
		{
			if (children == null)
			{
				return elements.contains(o);
			}
			else
			{
				for (QuadTreeNode<T> node : children)
				{
					if (node.contains(o))
					{
						return true;
					}
				}
			}
		}
		
		return false;
	}
	
	/**
	 * Renvoie un it�rateur pour les �l�ments que cette node contient. Ne permet pas de parcourir les �l�ments contenus
	 * dans les nodes filles.
	 */
	public Iterator<T> iterator()
	{
		return elements.iterator();
	}
	
	/**
	 * Ajoute un �l�ment dans cet arbre. <b>Attention</b> m�thode tr�s lourde. Pr�f�rer <code>addAll()</code> pour
	 * ajouter une grande quantit� de donn�es.
	 * 
	 * @param e
	 *            L'�l�ment � ajouter
	 * @return true
	 */
	public boolean add(T e)
	{
		if (children == null)
		{
			if (this.depth < treeRoot.maxNodeDepth && this.elements.size() + 1 > treeRoot.maxElementsPerNode)
			{
				this.elements.add(e);
				splitAndClear(this.elements);
			}
			else
			{
				this.elements.add(e);
			}
		}
		else
		{
			this.elements.add(e);
			splitAndClear(this.elements);
		}
		
		return true;
	}
	
	/**
	 * Ajoute tous les �l�ments � cette node. Split si besoin.
	 * 
	 * @param elementsToAdd
	 *            Les �l�ments � ajouter
	 * @return true
	 */
	public boolean addAll(Collection<? extends T> elementsToAdd)
	{
		this.elements.addAll(elementsToAdd);
		
		if (children == null)
		{
			if (this.depth < treeRoot.maxNodeDepth
			&& this.elements.size() + elementsToAdd.size() > treeRoot.maxElementsPerNode)
			{
				splitAndClear(this.elements);
			}
		}
		else
		{
			splitAndClear(this.elements);
		}
		
		return true;
	}
	
	/**
	 * Supprime une occurence de <code>o</code>.
	 * 
	 * @param o
	 *            L'objet � supprimer
	 * @return <code>true</code> si l'�l�ment a �t� supprim�
	 */
	public boolean remove(Object o)
	{
		if (elements.remove(o))
		{
			return true;
		}
		else
		{
			for (QuadTreeNode<T> node : children)
			{
				if (node.remove(o))
				{
					return true;
				}
			}
		}
		return false;
	}
	
	public void clear()
	{
		if (children != null)
		{
			for (QuadTreeNode<T> child : children)
			{
				child.clear();
			}
		}
		if (elements != null)
		{
			elements.clear();
		}
	}
	
	public int countNodes()
	{
		int total = 1; // this
		if (children != null)
		{
			for (QuadTreeNode<T> child : children)
			{
				total += child.countNodes();
			}
		}
		return total;
	}
}
